{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Water Bottles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numWaterBottles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #换水问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>超市正在促销，你可以用 <code>numExchange</code> 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 <code>numBottles</code> 瓶水。</p>\n",
    "\n",
    "<p>如果喝掉了水瓶中的水，那么水瓶就会变成空的。</p>\n",
    "\n",
    "<p>给你两个整数 <code>numBottles</code> 和 <code>numExchange</code> ，返回你 <strong>最多</strong> 可以喝到多少瓶水。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/19/sample_1_1875.png\" style=\"height: 240px; width: 480px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numBottles = 9, numExchange = 3\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>你可以用 <code>3</code> 个空瓶兑换 1 瓶水。\n",
    "所以最多能喝到 9 + 3 + 1 = 13 瓶水。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/19/sample_2_1875.png\" style=\"height: 240px; width: 790px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numBottles = 15, numExchange = 4\n",
    "<strong>输出：</strong>19\n",
    "<strong>解释：</strong>你可以用 <code>4</code> 个空瓶兑换 1 瓶水。\n",
    "所以最多能喝到 15 + 3 + 1 = 19 瓶水。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= numBottles &lt;= 100</code></li>\n",
    "\t<li><code>2 &lt;= numExchange &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [water-bottles](https://leetcode.cn/problems/water-bottles/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [water-bottles](https://leetcode.cn/problems/water-bottles/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['9\\n3', '15\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ksp = 0\n",
    "        h = 0\n",
    "        h += numBottles\n",
    "        ksp += numBottles\n",
    "        while 1:\n",
    "            a = ksp // numExchange\n",
    "            ksp -= a * numExchange\n",
    "            h += a\n",
    "            ksp += a\n",
    "            if ksp < numExchange:\n",
    "                break\n",
    "        return h\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "\n",
    "        drink = 0\n",
    "        drink += numBottles\n",
    "        while(1):\n",
    "            exc = numBottles // numExchange\n",
    "            rest = numBottles % numExchange\n",
    "            drink += exc\n",
    "\n",
    "            numBottles = exc + rest\n",
    "\n",
    "            if numBottles < numExchange:\n",
    "                break\n",
    "        \n",
    "        return drink"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        a=numBottles\n",
    "        k=numBottles\n",
    "        while a>=numExchange:\n",
    "            c=a//numExchange\n",
    "            b=a%numExchange\n",
    "            k+=c\n",
    "            a=c+b\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        s = m = numBottles\n",
    "        while m >= numExchange:\n",
    "            numBottles, m = divmod(m, numExchange)\n",
    "            s += numBottles\n",
    "            m += numBottles\n",
    "        return s\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:       \n",
    "         return numBottles + (numBottles - 1) // (numExchange - 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return numBottles + (numBottles - 1)// (numExchange - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res = rem = numBottles\n",
    "        while rem >= numExchange:\n",
    "             numBottles, rem = divmod (rem,numExchange)\n",
    "             res += numBottles;\n",
    "             rem += numBottles;\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res = numBottles\n",
    "        while numBottles >= numExchange:\n",
    "            x = numBottles // numExchange\n",
    "            y = numBottles % numExchange\n",
    "            res += x\n",
    "            numBottles = x + y\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        n = numBottles\n",
    "        m = numExchange\n",
    "        ans = n\n",
    "        while n>=m:\n",
    "            ans+=n//m\n",
    "            n = n%m+n//m\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        i=0\n",
    "        while(numBottles>=numExchange):\n",
    "            i+=numBottles//numExchange*numExchange\n",
    "            numBottles=numBottles//numExchange+numBottles%numExchange\n",
    "        i=i+numBottles\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res =rem =numBottles \n",
    "        while rem >= numExchange:\n",
    "            numBottles , rem = divmod (rem , numExchange) \n",
    "            res += numBottles \n",
    "            rem += numBottles\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        result = numBottles\n",
    "        while numBottles >= numExchange:\n",
    "            drinkBottles = numBottles // numExchange\n",
    "            result += drinkBottles\n",
    "            numBottles = drinkBottles + numBottles % numExchange\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        b,ans=numBottles,numBottles\n",
    "        while b >= numExchange:\n",
    "            b-=numExchange\n",
    "            ans += 1\n",
    "            b +=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "     res = rem =  numBottles\n",
    "     while rem >= numExchange:\n",
    "        numBottles,rem =divmod(rem,numExchange)\n",
    "        res += numBottles\n",
    "        rem += numBottles\n",
    "     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans=numBottles\n",
    "        while numBottles>=numExchange:\n",
    "            ans+=numBottles//numExchange\n",
    "            numBottles=numBottles//numExchange+numBottles%numExchange\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        maxn=numBottles\n",
    "        m=numBottles\n",
    "        while True:\n",
    "            maxn+=m//numExchange\n",
    "            m=m//numExchange+m%numExchange\n",
    "            if m<numExchange:\n",
    "                break\n",
    "        return maxn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res = rem = numBottles\n",
    "        while rem >= numExchange:\n",
    "            numBottles, rem = divmod(rem, numExchange)\n",
    "            res += numBottles\n",
    "            rem += numBottles\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans=0\n",
    "        empty=0\n",
    "        while True:\n",
    "            ans+=numBottles\n",
    "            numBottles,empty=divmod(numBottles+empty,numExchange)\n",
    "            if numBottles<1:break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        nums,ans=numBottles,numBottles\n",
    "        while nums>=numExchange:\n",
    "            nums-=numExchange\n",
    "            nums+=1\n",
    "            ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return(numBottles *numExchange - 1)//(numExchange-1)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        to_change = -1\n",
    "        left = -1\n",
    "        result = numBottles\n",
    "        while to_change != 0:\n",
    "             to_change=numBottles//numExchange\n",
    "             left = numBottles%numExchange\n",
    "             result += to_change\n",
    "             numBottles = to_change+left\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        bottle, ans = numBottles, numBottles\n",
    "        while bottle >= numExchange:\n",
    "            bottle -= numExchange\n",
    "            ans += 1\n",
    "            bottle += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return numBottles+(numBottles-1)//(numExchange-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res=rem=numBottles\n",
    "        while rem>=numExchange:\n",
    "              numBottles,rem=divmod(rem,numExchange)\n",
    "              res+=numBottles\n",
    "              rem+=numBottles\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        change = numBottles//numExchange\n",
    "        drink = numBottles\n",
    "        while change>0:\n",
    "            drink += change\n",
    "            sheng_yv = numBottles%numExchange\n",
    "            numBottles = change+sheng_yv\n",
    "            change =numBottles//numExchange\n",
    "        return drink\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res = rem = numBottles\n",
    "        while rem >= numExchange:\n",
    "             numBottles, rem = divmod(rem, numExchange)\n",
    "             res += numBottles\n",
    "             rem += numBottles\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        empty=total=numBottles\n",
    "        while empty >= numExchange:\n",
    "            full,empty=divmod(empty,numExchange)\n",
    "            total += full\n",
    "            empty += full\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        drink = numBottles\n",
    "        empty = numBottles\n",
    "        while(empty >= numExchange):\n",
    "            drink += empty // numExchange\n",
    "            empty = empty//numExchange + empty % numExchange\n",
    "        return(drink)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return numBottles+(numBottles-1)//(numExchange-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        total = 0\n",
    "        empty_bott = 0  # 空瓶子\n",
    "        while empty_bott >= numExchange or numBottles > 0:\n",
    "            print(numBottles, empty_bott)\n",
    "            total += numBottles  # 喝掉\n",
    "            empty_bott = numBottles + empty_bott\n",
    "            # empty_bott = (numBottles + empty_bott) % numExchange  # 空瓶子\n",
    "            numBottles = empty_bott // numExchange  # 换来的酒\n",
    "            empty_bott = empty_bott % numExchange\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "       ans = numBottles\n",
    "       NewKong = numBottles\n",
    "       while numBottles >= numExchange:\n",
    "           NewWater = numBottles // numExchange\n",
    "           ans += NewWater\n",
    "           NewKong = NewWater +numBottles % numExchange\n",
    "           numBottles = NewKong\n",
    "       return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        hele=numBottles#喝水的数量\n",
    "        keyihuan=numBottles#换水的瓶子数\n",
    "        while keyihuan>=numExchange:#当空瓶子比可以换水数大的时候\n",
    "            new=keyihuan//numExchange#新的换水的瓶子数\n",
    "            hele+=new#之前喝过的加上新换的\n",
    "            keyihuan=new+(keyihuan-new*numExchange)#换水瓶子数是之前的没换完的加上新换的\n",
    "        return hele"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        s = numBottles\n",
    "        while numBottles > numExchange-1:\n",
    "            s += (numBottles // numExchange)\n",
    "            numBottles = numBottles // numExchange + numBottles % numExchange         \n",
    "            print(s,numBottles)\n",
    "        # if numExchange - numBottles % numExchange == 1:\n",
    "        #     s += 1\n",
    "        #     print(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        bottle, ans = numBottles, numBottles\n",
    "        while bottle >= numExchange:\n",
    "            bottle -= numExchange\n",
    "            ans += 1\n",
    "            bottle += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        T=0\n",
    "        while True:\n",
    "            mod=numBottles%numExchange\n",
    "            T+=numBottles-mod\n",
    "            numBottles=numBottles//numExchange+mod\n",
    "            if numBottles<numExchange:\n",
    "                T+=numBottles\n",
    "                break\n",
    "        return T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "\n",
    "        res = 0\n",
    "        res = res + numBottles\n",
    "        while(numBottles >= numExchange):\n",
    "            \n",
    "            res = res + (int)(numBottles / numExchange)\n",
    "            numBottles = (int)(numBottles / numExchange) + numBottles % numExchange\n",
    "            print('res',res, numBottles)\n",
    "        # if( numBottles == numExchange - 1):\n",
    "        #     res = res + 1\n",
    "        print(res)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        a=numBottles\n",
    "        while True:\n",
    "            if numBottles>=numExchange:\n",
    "                numBottles=numBottles-numExchange\n",
    "                numBottles=numBottles+1\n",
    "                a=a+1\n",
    "            else:\n",
    "                return a\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return (d := numBottles // numExchange) * numExchange + self.numWaterBottles(d + numBottles % numExchange, numExchange) if numBottles >= numExchange else numBottles\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans = numBottles\n",
    "        while numBottles >= numExchange:\n",
    "            new = numBottles // numExchange\n",
    "            ans += new\n",
    "            numBottles = new + (numBottles % numExchange)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        water=0\n",
    "        while numBottles-numExchange>=0:\n",
    "            water=water+numExchange\n",
    "            numBottles=numBottles-numExchange+1\n",
    "        water=water+numBottles\n",
    "        return water"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "            c=0                         #累加兑换水\n",
    "            d=0\n",
    "            a=numBottles//numExchange   #可以兑换多少瓶水  5\n",
    "            b=numBottles % numExchange  #兑换水之后剩下的瓶子 2 \n",
    "            while True:\n",
    "                if a+b>=numExchange:     #            7\n",
    "                    d=a+b\n",
    "                    c+=a                  #          5\n",
    "                    a=(d)//numExchange  #          2\n",
    "                    b=(d)-(a*numExchange)  #   出问题！    \n",
    "                    \n",
    "                else:\n",
    "                    return numBottles+a+c "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans = numBottles\n",
    "        y = 0\n",
    "        while numBottles >= numExchange:\n",
    "            y = numBottles % numExchange\n",
    "            numBottles = numBottles // numExchange\n",
    "            ans += numBottles\n",
    "            numBottles = numBottles + y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res = rem = numBottles \n",
    "        while rem >= numExchange:\n",
    "            numBottles,rem = divmod(rem,numExchange)\n",
    "            res += numBottles\n",
    "            rem += numBottles\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return numBottles + (numBottles - 1) // (numExchange - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        drink_sum = empty_bottles = numBottles\n",
    "        while empty_bottles >= numExchange:\n",
    "            exchange = empty_bottles // numExchange  # 换的水瓶数\n",
    "            drink_sum += exchange  # 总共喝的水瓶数\n",
    "            empty_bottles = exchange + empty_bottles % numExchange  # 剩下的空瓶数\n",
    "        return drink_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res = rem = numBottles \n",
    "        while rem >= numExchange:\n",
    "            numBottles , rem = divmod ( rem , numExchange )\n",
    "            res += numBottles\n",
    "            rem += numBottles\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        bottle,ans = numBottles,numBottles\n",
    "        while bottle>=numExchange:\n",
    "            bottle -= numExchange\n",
    "            ans += 1\n",
    "            bottle += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        sum=numBottles\n",
    "        while numBottles//numExchange>=1:\n",
    "            sum=sum+(numBottles//numExchange)\n",
    "            numBottles=(numBottles//numExchange)+numBottles%numExchange\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "\n",
    "        ans = numBottles # 买了多少 喝了多少\n",
    "        newKong = numBottles\n",
    "        while numBottles >= numExchange:\n",
    "            newWater = numBottles // numExchange # 又能喝多少\n",
    "            ans += newWater\n",
    "            newKong = numBottles % numExchange + newWater # 剩几个空瓶子\n",
    "            numBottles = newKong\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        drinkBottles = numBottles\n",
    "        freeBottles = numBottles\n",
    "        while (freeBottles >= numExchange):\n",
    "            tmp = freeBottles // numExchange\n",
    "            drinkBottles = drinkBottles + tmp\n",
    "            freeBottles = tmp + freeBottles % numExchange\n",
    "        return drinkBottles\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, emptyBottles: int, numExchange: int) -> int:\n",
    "        ans, emptyBottles = emptyBottles, emptyBottles\n",
    "        while emptyBottles >= numExchange:\n",
    "            ans += emptyBottles // numExchange\n",
    "            emptyBottles = emptyBottles // numExchange + emptyBottles % numExchange\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        n=numBottles\n",
    "        ans=0\n",
    "        last=0\n",
    "        while n>0:\n",
    "            ans+=n\n",
    "            last+=n\n",
    "            n=last//numExchange\n",
    "            last%=numExchange\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return (numBottles - numExchange) // (numExchange - 1) + 1 + numBottles if numBottles >= numExchange else numBottles\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        count=numBottles\n",
    "        while numBottles>=numExchange:\n",
    "            numbuywater=numBottles//numExchange\n",
    "            numwater=numBottles % numExchange\n",
    "            count+=numbuywater\n",
    "            numBottles=numbuywater+numwater\n",
    "        return count\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        drink = numBottles\n",
    "        bottle = numBottles\n",
    "        while bottle >= numExchange:\n",
    "            exchange = bottle // numExchange\n",
    "            drink += exchange\n",
    "            bottle = exchange + (bottle % numExchange)\n",
    "        return drink"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        bottle, ans = numBottles, numBottles\n",
    "        while bottle >= numExchange:\n",
    "            bottle -= numExchange\n",
    "            ans += 1\n",
    "            bottle += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        res  = numBottles\n",
    "        while numBottles >= numExchange:\n",
    "            res += numBottles // numExchange\n",
    "            numBottles = numBottles // numExchange + numBottles % numExchange\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans, numBottles  = numBottles, numBottles\n",
    "        while numBottles >= numExchange:\n",
    "            numBottles -= numExchange\n",
    "            ans += 1\n",
    "            numBottles += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return (numBottles * numExchange - 1) // (numExchange - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        return numBottles + (numBottles - 1) // (numExchange - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        if not numBottles % (numExchange - 1): return numBottles+numBottles // (numExchange - 1) - 1\n",
    "        return numBottles+numBottles // (numExchange - 1)\n",
    "'''\n",
    "考虑每一次交换的结果。用K个酒瓶换一瓶酒，实际上的结果是：瓶子减少K-1个，能喝的酒增加1瓶。\n",
    "所以只要考虑一共能做多少次交换，就可以得出有多少瓶新增的酒。\n",
    "初始有N瓶酒，一共能做N/(K-1)次交换，也就是增加了N/(K-1)瓶酒。要注意最后一次交换，如果最后一次刚好剩下K-1瓶，实际上是少了一瓶，不能交换。\n",
    "再加上初始的N瓶酒，就得到了结果。\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        count=0\n",
    "        temp=0\n",
    "        bottle=0\n",
    "        \n",
    "           \n",
    "        while numBottles!=0:\n",
    "            count+=numBottles\n",
    "            chansheng_bottle=numBottles\n",
    "            null_bottle=bottle+chansheng_bottle\n",
    "            water=null_bottle//numExchange\n",
    "            bottle=null_bottle%numExchange\n",
    "            numBottles=water\n",
    "        return count\n",
    "       \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        bottle, ans = numBottles, numBottles\n",
    "        while bottle >= numExchange:\n",
    "            bottle -= numExchange\n",
    "            ans += 1\n",
    "            bottle += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans = 0\n",
    "        kong = 0\n",
    "        temp = 0\n",
    "        while numBottles>0:\n",
    "            ans += numBottles\n",
    "            Bottles = numBottles\n",
    "            numBottles = (Bottles + temp) // numExchange\n",
    "            temp = (Bottles + temp) % numExchange\n",
    "            \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        ans = numBottles\n",
    "        add = numBottles // numExchange\n",
    "        while add >= 1: \n",
    "            add = numBottles // numExchange\n",
    "            rest = numBottles % numExchange\n",
    "            ans += add\n",
    "            numBottles = rest + add\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        maxWater = numBottles\n",
    "        emptyBot = numBottles\n",
    "        while True:\n",
    "            exchange = emptyBot // numExchange  # number of new bottles\n",
    "            maxWater += exchange\n",
    "            emptyBot = emptyBot - (numExchange * exchange) + exchange   # updated empty\n",
    "            if emptyBot < numExchange:\n",
    "                return maxWater    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:\n",
    "        cur = numBottles\n",
    "        res = cur + cur // numExchange\n",
    "        while cur >= numExchange:\n",
    "            cur = cur // numExchange + cur % numExchange\n",
    "            res += cur // numExchange\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
